`:top
A `!binary expression tree`! is a specific kind of a `F33f`_`[binary tree`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Binary_tree]`_`f used to represent `F33f`_`[expressions`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Expression_(mathematics)]`_`f. Two common types of expressions that a binary expression tree can represent are `F33f`_`[algebraic`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Algebra]`_`f`:cite-ref-brpreiss-1-0[`F5bf`_`[1`#cite-note-brpreiss-1]`_`f] and `F33f`_`[boolean`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Boolean_algebra]`_`f. These trees can represent expressions that contain both `F33f`_`[unary`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Unary_operation]`_`f and `F33f`_`[binary`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Binary_function]`_`f operators.`:cite-ref-brpreiss-1-1[`F5bf`_`[1`#cite-note-brpreiss-1]`_`f]
Like any binary tree, each node of a binary expression tree has zero, one, or two children. This restricted structure simplifies the processing of expression trees.
>>Contents
• `F0af`_`[Construction of an expression tree`#construction-of-an-expression-tree]`_`f
• `F0af`_`[Example`#example]`_`f
• `F0af`_`[Algebraic expressions`#algebraic-expressions]`_`f
• `F0af`_`[Boolean expressions`#boolean-expressions]`_`f
• `F0af`_`[See also`#see-also]`_`f
• `F0af`_`[References`#references]`_`f
-─
>>Construction of an expression tree
>>>Example
The input in postfix notation is: a b + c d e + * * Since the first two symbols are operands, one-node trees are created and pointers to them are pushed onto a stack. For convenience the stack will grow from left to right.
The next symbol is a '+'. It pops the two pointers to the trees, a new tree is formed, and a pointer to it is pushed onto the stack.
Next, c, d, and e are read. A one-node tree is created for each and a pointer to the corresponding tree is pushed onto the stack.
Continuing, a '+' is read, and it merges the last two trees.
Now, a '*' is read. The last two tree pointers are popped and a new tree is formed with a '*' as the root.
Finally, the last symbol is read. The two trees are merged and a pointer to the final tree remains on the stack.`:cite-ref-gopal2010-353-2-0[`F5bf`_`[2`#cite-note-gopal2010-353-2]`_`f]
>>Algebraic expressions
Algebraic expression trees represent expressions that contain `F33f`_`[numbers`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Number]`_`f, `F33f`_`[variables`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Variable_(mathematics)]`_`f, and unary and binary operators. Some of the common operators are × (`F33f`_`[multiplication`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multiplication]`_`f), ÷ (`F33f`_`[division`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Division_(mathematics)]`_`f), + (`F33f`_`[addition`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Addition]`_`f), − (`F33f`_`[subtraction`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Subtraction]`_`f), ^ (`F33f`_`[exponentiation`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Exponentiation]`_`f), and - (`F33f`_`[negation`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Negation]`_`f). The operators are contained in the `F33f`_`[internal nodes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Internal_node]`_`f of the tree, with the numbers and variables in the `F33f`_`[leaf nodes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Leaf_nodes]`_`f.`:cite-ref-brpreiss-1-2[`F5bf`_`[1`#cite-note-brpreiss-1]`_`f] The nodes of binary operators have two `F33f`_`[child nodes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Child_nodes]`_`f, and the unary operators have one child node.
>>Boolean expressions
Boolean expressions are represented very similarly to algebraic expressions, the only difference being the specific values and operators used. Boolean expressions use `*true`* and `*false`* as constant values, and the operators include ∧ ∧ {\\displaystyle \\land } (`F33f`_`[AND`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Logical_and]`_`f), ∨ ∨ {\\displaystyle \\lor } (`F33f`_`[OR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Logical_or]`_`f), ¬ ¬ {\\displaystyle \\neg } (`F33f`_`[NOT`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Logical_not]`_`f).
>>See also
• `F33f`_`[Expression (mathematics)`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Expression_(mathematics)]`_`f
• `F33f`_`[Term (logic)`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Term_(logic)]`_`f
• `F33f`_`[Context-free grammar`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Context-free_grammar]`_`f
• `F33f`_`[Parse tree`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Parse_tree]`_`f
• `F33f`_`[Abstract syntax tree`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Abstract_syntax_tree]`_`f
>>References
`:cite-note-brpreiss-1`!1.`! `F0af`_`[↑`#cite-ref-brpreiss-1-0]`_`f `:citerefbruno-r-preiss1998`aBruno R. Preiss (1998). "Expression Trees". Archived from the original on January 19, 2017. Retrieved December 20, 2010.
`:cite-note-gopal2010-353-2`!2.`! `F0af`_`[↑`#cite-ref-gopal2010-353-2-0]`_`f Gopal, Arpita. `*Magnifying Data Structures`*. PHI Learning, 2010, p. 353.
`c`F0af`_`[↑ Back to top`#top]`_`f`a